package backtrack

/*
二叉树递归用 把未知递归函数当已知来使用的三段法(一个根节点，两个孩子节点)
一般的递归和回溯 把未知递归函数当已知来使用的二段法(一个开始节点，开始节点之后的所有节点看作一个整体)
*/

// 山下左右四个方向
var directions = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func exist(board [][]byte, word string) bool {
	m, n := len(board), len(board[0])
	// 记录每次搜索过程中已搜索过的节点，避免重复搜索
	visited := make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	// i,j用来标志目前搜索到的board节点，k表示搜索到的word长度
	var backtrack func(i, j, k int) bool
	backtrack = func(i, j, k int) bool {
		// 如果在搜索过程中发现单词不匹配，直接返回，不再继续搜索
		if board[i][j] != word[k] {
			return false
		}
		// 搜索到整个单词
		if k == len(word)-1 {
			return true
		}
		// 每搜索完一个节点，将visited设置成true，回溯回来之后再设置为false
		visited[i][j] = true
		// 每搜索完一个字母，则继续向上下左右四个方向搜索
		for _, d := range directions {
			x, y := i+d[0], j+d[1]
			// 注意，这里容易遗漏!visited[i][j]，只访问未曾访问过的节点
			if x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] {
				// 这里将backtrack函数当作已知来使用，即表示搜索第一个节点之后的部分是否成功
				if backtrack(x, y, k+1) {
					return true
				}
			}
		}
		visited[i][j] = false
		return false
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if backtrack(i, j, 0) {
				return true
			}
		}
	}
	return false
}
